Some search algorithms, such as breadth-first search or minimax search are deterministic: if you rerun the algorithm it will give exactly the same answer ever time. However, other search algorithms, such as simulated annealing, include random steps. These stocastic searches can be very powerful for large or complex problems, but will take a different search path, and potentially give a different result evey time they are run. This can be an advantage, for example re-running hill climbing from different random start points can avoid some of the problens of local minima or local maxima.
Also known as stochastic tree search